
#Search algorithms




def SequentialSearch(A, Lb,Ub,Key, verbose=0):
    """
    sage: SequentialSearch([1,7,-15,23,2],0,4,23)
    23
    sage: SequentialSearch([1,7,-15,23,2],0,4,23)
    -1
    """
    i = Lb
    while True:
        # Lb <= i < Ub
        # Lb <= k < i  \implies  A[k] != key
        
        if verbose: print i,Lb,Ub,Key
            
        if not i <= Ub:
            return -1

        if A[i] == Key:
            return i

        i = i + 1





def BinarySearch(A, Lb, Ub, Key,verbose=0):
    i = (Lb + Ub) // 2
    while True:
        #exists j . A[j] = Key \implies Lb <= j <= Ub
        print A, i, Lb, Ub, Key
        if not Lb <= Ub: break
        
        if Key > A[i]:
            Lb = i + 1
        elif Key < A[i]:
            Ub = i - 1
        else:
            return i
        i = (Lb + Ub) // 2

    return -1#-(Lb+1)
  

def acopy(A,B,N,it=1):
    i = 0
    B_ = [b for b in B]
    #\forall k. 0<=k<i \implies (B[k]=A[k] \wedge k<N)
    print 'i N A B_'
    while True:
        print i,N,arr2str(A),B_
        if not i < N: break
            
        
        B_[i]=A[i]
        i = i + it

    return A,B_



def partition(A,B,C,N):
    i = 0
    j = 0
    k = 0
    print 'i N A B C'
    while True:
        #\forall x. 0<=x<j \implies (x < N \wedge C[x]>=0) \wedge  
        #\forall x. 0<=x<k \implies (x < N \wedge B[x]<0)*/

        print i,j,k,N,A,B,C
        
        if not i < N: break
            
        if (A[i] >= 0):
            B[j] = A[i]
            j = j + 1;
        else:
            C[k] = A[i]
            k = k + 1
            
        i = i + 1;

    return A,B,C



def mymult(A,B):
    x = A
    y = B
    z = 0
    while x > 0:
        if mod(x,2)==1:
            print 'hi'
            z = z + y
        y = 2*y
        x = x//2

    return z
